/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.graph.dfs;

/**
 * <p>
 * 单词查找【超时了】
 * 
 * 判断一个单词是否在二维数组中，每个位置的字符只能用一次
 * 例如
 *   ["ABCE"],
 *   ["SFCS"],
 *   ["ADEE"]
 * word = "ABCCED", -> returns true,
 * word = "SEE", -> returns true,
 * word = "ABCB", -> returns false.  
 * </p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月28日
 */
public class WordSearch {

  public boolean exist(char[][] board, String word) {
      //初始条件判断
      if(board== null || board.length==0 || board[0].length==0){
          return false;
      }
      //二维数组记录每个位置的访问情况
      int m = board.length;
      int n = board[0].length;
      boolean[][] visited = new boolean[m][n];
      for(int i=0;i<m;i++){
          for(int j=0;j<n;j++){
              //从每个格子开始找
              if(isExistDfs(board,i,j,word,visited)){
                  return true;
              }
          }
      }
      return false;
    }

/**
 * @param board
 * @param i
 * @param j
 * @param word
 * @param visited
 * @return
 * @author towan
 * 2015年5月28日
 */
private boolean isExistDfs(char[][] board, int i, int j, String word, boolean[][] visited) {
    if(word.length()==0 || (word.length()==1 && word.charAt(0)==board[i][j])){
        return true;
    }
    //比较当前第一个字符
    if(word.charAt(0)!=board[i][j]){
        return false;
    }
    visited[i][j] = true;
    //截取第一个以后的字符
    String subWord = word.substring(1);
    if(i+1<board.length && !visited[i+1][j]){
        if(isExistDfs(board, i+1, j, subWord, visited)){
            return true;
        }
    }
    if(j+1<board[0].length && !visited[i][j+1]){
        if(isExistDfs(board, i, j+1, subWord, visited)){
            return true;
        }
    }
    if(i-1>0 && !visited[i-1][j]){
        if(isExistDfs(board, i-1, j, subWord, visited)){
            return true;
        }
    }
    if(j-1>0 && !visited[i][j-1]){
        if(isExistDfs(board, i, j-1, subWord, visited)){
            return true;
        }
    }
    //重置
    visited[i][j] = false;
    return false;
}


}
